// If run with -inline 300 there are some sigma nodes whose incoming
// values do not have any conditional branch associated (only
// unconditional). We were assuming that all sigma nodes are
// associated with conditional branch.
// This problem was observed by Andre Oliveira Maroneze (07/02/13).

#include <stdio.h>
/*
 * The Computer Lannguage Shootout
 * http://shootout.alioth.debian.org/
 * Contributed by Heiner Marxen
 *
 * "fannkuch"	for C gcc
 *
 * $Id: fannkuch-gcc.code,v 1.33 2006/02/25 16:38:58 igouy-guest Exp $
 */

#define Int	int
#define Aint	int

    static long
fannkuch( int n )
{
	Aint*	perm;
	Aint*	perm1;
	Aint*	count;
	long	flips;
	long	flipsMax;
	Int		r;
	Int		i;
	Int		k;
	Int		didpr;
	const Int	n1	= n - 1;

	if( n < 1 ) return 0;

	perm  = calloc(n, sizeof(*perm ));
	perm1 = calloc(n, sizeof(*perm1));
	count = calloc(n, sizeof(*count));

	for( i=0 ; i<n ; ++i ) {
		perm1[i] = i;
	}	/* initial (trivial) permu */

	r = n; didpr = 0; flipsMax = 0;
	for(;;) {
		if( didpr < 30 ) {
			for( i=0 ; i<n ; ++i ) { 
				printf("%d", (int)(1+perm1[i]));
			}
			printf("\n");
			++didpr;
		}
		for( ; r!=1 ; --r ) {
			count[r-1] = r;
		}

#define XCH(x,y)	{ Aint t_mp; t_mp=(x); (x)=(y); (y)=t_mp; }
		if( ! (perm1[0]==0 || perm1[n1]==n1) ) {
			flips = 0;
                        // NOTE: this line causes an error when -inline 1 (or greater) is used
                        if (flips) { flips = flips+0; };
			for( i=1 ; i<n ; ++i ) {	/* perm = perm1 */
				perm[i] = perm1[i];
			}
			k = perm1[0];		/* cache perm[0] in k */
			do {			/* k!=0 ==> k>0 */
				Int	j;
				for( i=1, j=k-1 ; i<j ; ++i, --j ) {
					XCH(perm[i], perm[j])
				}
				++flips;
				/*
				* Now exchange k (caching perm[0]) and perm[k]... with care!
				* XCH(k, perm[k]) does NOT work!
				*/
				j=perm[k];
				perm[k]=k;
				k=j;
			}while( k );
			if( flipsMax < flips ) {
				flipsMax = flips;
			}
		}

		for(;;) {
			if( r == n ) {
				return flipsMax;
			}
			/* rotate down perm[0..r] by one */
			{
				Int	perm0 = perm1[0];
				i = 0;
				while( i < r ) {
					k = i+1;
					perm1[i] = perm1[k];
					i = k;
				}
				perm1[r] = perm0;
			}
			if( (count[r] -= 1) > 0 ) {
				break;
			}
			++r;
		}
	}
}

    int
main( int argc, char* argv[] )
{
    int n = (argc>1) ? atoi(argv[1]) : 10;
    printf("Pfannkuchen(%d) = %ld\n", n, fannkuch(n));
    return 0;
}
